home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8367 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.2 KB
  1. Path: whale.st.usm.edu!cwcurry
  2. From: cwcurry@whale.st.usm.edu (Conrad Walter Curry)
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Followup-To: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  6. Date: 17 Feb 1996 05:57:30 GMT
  7. Organization: University of Southern Mississippi
  8. Message-ID: <4g3qoa$pho@thorn.cc.usm.edu>
  9. References: <4fr8be$ass@news.iconn.net>
  10. NNTP-Posting-Host: whale.st.usm.edu
  11. X-Newsreader: TIN [version 1.2 PL1]
  12.  
  13. The Crow (thecrow@iconn.net) wrote:
  14. : Here is what I am trying to do, I want to find the last NON-ZERO digit of a 
  15. : given factorial.  For instance,
  16.  
  17. : 5! = 120
  18.  
  19. : so the last non-zero digit is 2.  I want to be able to do this up to 1000.  
  20. : Problem is, no matter how huge of a data-type you use, there isn't any way
  21. : for 
  22. : the computer to handle 1000!, it is however possible to find the last non-
  23. : zero 
  24. : digit somehow.  One thing I have tried is as I went through mulitplying the 
  25. : series of numbers in the factorial (5 * 4 * 3 * 2) I would remove all the 
  26. : trailing ZEROS, I got this to work up to 789, but it wont work with 1000 and 
  27. : i
  28. : am not really sure why.  If anyone has a clue how I can do this let me know.
  29.  
  30. : -- 
  31. : The Crow - thecrow@iconn.net
  32. : "It can't rain all the time"
  33. : -Kryptology
  34.  
  35.  
  36.   I don't know a formula for the kth digit of N!, but going ahead and
  37. computing all of N! isn't that hard.  Use multiprecision arithmetic.
  38. Put each digit into an array element.  The base used is usually the word
  39. size of the computer, but for this case base 10 would be easier to
  40. understand.
  41.   Initialize an array U[1]=1 and a variable UL=1 which is the length of
  42. the array.
  43.   
  44.   for j := 2 to N do   
  45.    begin
  46.     for i := 1 to UL do
  47.      U[i] := U[i]*j;
  48.     
  49.      Now Normalize the array.
  50.  
  51.      for i := 1 to UL do
  52.       begin
  53.        U[i+1] := U[i] div 10;
  54.        if (i=UL) and (U[i+1]<>0) then UL := UL+1;
  55.        U[i] := U[i] mod 10;
  56.       end;
  57.  
  58.    end;
  59.  
  60.   This is simple paper and pencil type arithmetic and shouldn't be hard
  61. to follow.  Using Stirling's formula for N! the size of the array needed
  62. for this is approximately log N! = log N + N log(N/exp(1)) for 1000! that
  63. would be 2568 digits or array elements.
  64.